A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
The packets are transmitted between the source device and destination device using intermediate network devices, such as gateways, firewalls, switches and routers. When a network receives an incoming packet or sends an outgoing packet, the network device may apply one or more filters to the packet to perform a defined action on the packet under certain conditions. In order to identify the terms of the filters to apply to a given packet, the network device may extract information from the packet, such as a source or destination Internet Protocol (IP) address, a source or destination port, and protocol. The network device then performs a search of the filter terms installed within the network device to determine whether the extracted information satisfies criteria specified by any of the filter terms.
One conventional approach to identifying matching filter terms to apply to packets includes applying a hash function to at least a portion of the extracted information (i.e., a key) to determine possible locations in a hash table for the extracted information. A key corresponds to a portion of the extracted information having a predefined length (e.g., a prefix of a source or destination IP address). That is, one or more keys are inputted into a hash function to generate one or more possible locations in a hash table. The network device then looks up each possible location in the hash table to determine if the key is found in any of the possible locations. A key is found in the hash table when one or more filter terms are defined for the possible location. According to a longest prefix match algorithm, the router applies the filter terms associated with the longest prefix for which a match is found for the corresponding key in the hash table. Performing the lookup for each key in the hash table is done serially, such that each possible location for the extracted information is looked up in the hash table one location at a time.
In order to improve the speed at which the network device identifies filter terms to apply to the packets, the network device may be configured to minimize the number of lookups in the hash table. In some cases, the network device may utilize a Bloom filter as an initial assessment of whether the key is affirmatively not present within the hash table or, alternatively, whether the key may possibly be stored in the hash table. In this way, the Bloom filter may provide an efficient mechanism for avoiding computationally expensive searches of a hash table when the key is affirmatively not present within the hash table. Conventionally, the Bloom filter is implemented as a bit array that stores one 1-bit value at each entry of the array, where each 1-bit entry may correspond to a different “bucket” of a corresponding hash table and indicate that at least one entry in the hash table exists for that particular “bucket.” When the Bloom filter is implemented in hardware (e.g., when the bit array is stored in multiple memory banks), the network device may perform a look up for multiple keys in the Bloom filter in parallel, reducing the total number of clock cycles required to look up all of the keys generated for the extracted information. However, when a large number of search keys all require reads from the same memory bank, the queue for the memory bank may become full and force the scheduling component of the router to stall, so that the scheduler cannot issue lookup requests to any of the memory banks of the Bloom filter until the queue is no longer full. Thus, the memory bank having the full queue may be a bottleneck that limits the overall throughput of the Bloom filter lookups and operation of the network device.